# 队列(Queue)
# 1.队列是一个数据集合，仅允许在列表的一端进行插入，另一端进行删除。
# 2.进行插入的一端称为对尾(rear)，插入动作称为进队或入队
# 3.进行删除的一端称为对头(front)，删除动作称为出队
# 4.队列的性质先进先出(First-in,First-out)
# 队列的实现方式--环形队列
# 环形队列：当队尾front==Maxsize + 1时，再前进一个位置自动到0.
# 队首指针前进1：front=(front+1)%Maxsize
# 队尾指针前进1：rear==(rear+1)%Maxsize
# 对空条件：rear==front
# 队满条件：(rear+1)%Maxsize==front
# 为什么要用环形队列
# 因为在列表中删除第一个元素和删除最后一个元素花费的时间代价是不一样的，删除列表的第一个元素，那么在它之后的所有的元素都要进行移动，环形队列没有删除操作只有修改操作，从而提高了效率
# 例如用列表模拟一个12个元素的队列实际最多存放11个 如果存放了12个就无法判断是队满状态还是对空状态
from collections import deque


class Queue(object):
    def __init__(self, size=100):
        self.queue = [0 for i in range(size)]
        self.size = size
        # 队尾指针
        self.rear = 0
        # 队首指针
        self.front = 0

    # 入队
    def push(self, element):
        # 如果队不满才可以入队
        if not self.is_filled():
            self.rear = (self.rear + 1) % self.size
            self.queue[self.rear] = element
        else:
            raise IndexError('Queue is filled')

    # 出队
    def pop(self):
        # 如果队列不为空
        if not self.is_empty():
            self.front = (self.front + 1) % self.size
            return self.queue[self.front]
        else:
            raise IndexError('Queue is empty')

    # 是否队空
    def is_empty(self):
        return self.rear == self.front

    # 是否队满
    def is_filled(self):
        return (self.rear + 1) % self.size == self.front


q = Queue(10)
q.push(1)
q.pop()

# 双向队列
# 双向队列的两端都支持进队和出队的操作
# 双向队列的基本操作
# 队首进队
# 队首出队
# 队尾进队
# 队尾出队
# python中双向队列的使用

q1 = deque()
# 队尾进队
q1.append(1)
# 队首出队
q1.popleft()
# 队首进队
q1.appendleft()
# 队尾出队
q1.pop()
